package metis;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Stack;

/**
 * The <tt>Graph</tt> class represents an undirected graph of vertices named 0 through V-1. It supports the following operations: add an edge to the graph, iterate over all of the neighbors adjacent to a vertex. Parallel edges and self-loops are
 * permitted.
 * <p>
 * For additional documentation, see <a href="http://algs4.cs.princeton.edu/51undirected">Section 5.1</a> of <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 */
public class Graph {
	private final int V;
	private int E;
	private HashMap<Integer, HashSet<Integer>> adj;

	/**
	 * Create an empty graph with V vertices.
	 */
	public Graph(int V) {
		if (V < 0)
			throw new RuntimeException("Number of vertices must be nonnegative");
		this.V = V;
		this.E = 0;
		adj = new HashMap<Integer, HashSet<Integer>>();
	}

	/**
	 * Create a random graph with V vertices and E edges. Expected running time is proportional to V + E.
	 */
	public Graph(int V, int E) {
		this(V);
		if (E < 0)
			throw new RuntimeException("Number of edges must be nonnegative");
		for (int i = 0; i < E; i++) {
			int v = (int) (Math.random() * V);
			int w = (int) (Math.random() * V);
			addEdge(v, w);
		}
	}

	/**
	 * Return the number of vertices in the graph.
	 */
	public int V() {
		return V;
	}

	/**
	 * Return the number of edges in the graph.
	 */
	public int E() {
		return E;
	}

	/**
	 * Add the undirected edge v-w to graph.
	 */
	public void addEdge(int v, int w) {
		HashSet<Integer> tmp;
		if (v != w) {
			E++;
			if (adj.containsKey(v)) {
				tmp = adj.get(v);
				tmp.add(w);
			} else {
				tmp = new HashSet<Integer>();
				tmp.add(w);
				adj.put(v, tmp);
			}
			if (adj.containsKey(w)) {
				tmp = adj.get(w);
				tmp.add(v);
			} else {
				tmp = new HashSet<Integer>();
				tmp.add(v);
				adj.put(w, tmp);
			}
		}

	}

	/**
	 * Return the list of neighbors of vertex v as in Iterator.
	 */
	public Iterator<Integer> adj(int v) {
		return adj.get(v).iterator();
	}

	public HashSet<Integer> neighbours(int v) {
		return adj.get(v);
	}

	/**
	 * Return a string representation of the graph.
	 */
	public String toString() {
		StringBuilder s = new StringBuilder();
		String NEWLINE = System.getProperty("line.separator");
		Iterator<Integer> it;
		int w;
		s.append(V + " vertices, " + E + " edges " + NEWLINE);
		for (int v = 0; v < V; v++) {
			s.append(v + ": ");
			it = adj.get(v).iterator();
			while (it.hasNext()) {
				w = it.next();
				s.append(w + " ");
			}
			s.append(NEWLINE);
		}
		return s.toString();
	}
}